package com.gxc.string;

/**
 * 给定一个只由 0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的字符串express，
 * 再给定一个布尔值 desired。
 * 返回express能有多少种组合方式，可以达到desired的结果。
 * [举例]
 * express="1^0|0|1"，desired=false
 * 只有 1^((0|0)|1)和 1^(0|(0|1))的组合可以得到 false，返回 2。
 * express="1"，desired=false
 * 无组合则可以得到false，返回0
 *
 * 解法：
 * 尝试以每个逻辑运算符位置分割 ****x*****，()逻辑运算符()
 * 根据期望值不同。走不同的递归流程
 */
public class Combination {

    public static void main(String[] args) {
        String express = "1^0|0|1";
        boolean desired = false;
        System.out.println(process(express, desired));

        express = "1";
        desired=false;
        System.out.println(process(express, desired));
    }

    public static int process(String express, boolean desired) {
        char[] chars = express.toCharArray();
        if (!isValid(chars)) {
            return 0;
        }
        return resolve(chars, 0, chars.length-1, desired);
    }

    private static int resolve(char[] chars, int start, int end, boolean desired) {
        if (start == end) {
            if (chars[start] == '1' && desired == true) {
                return 1;
            } else if (chars[start] == '0' && desired == false) {
                return 1;
            } else {
                return 0;
            }
        }

        int sum = 0;
        for (int i = start; i <= end; i++) {
            if (isOperator(chars[i])) {
                if (chars[i] == '^') {
                    if (desired) {
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, false);
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, true);
                    } else {
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, true);
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, false);
                    }

                } else if (chars[i] == '&') {
                    if (desired) {
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, true);
                    } else {
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, false);
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, true);
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, false);
                    }

                } else if (chars[i] == '|') {
                    if (desired) {
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, false);
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, true);
                        sum += resolve(chars, start, i-1, true) * resolve(chars, i+1, end, true);
                    } else {
                        sum += resolve(chars, start, i-1, false) * resolve(chars, i+1, end, false);
                    }

                }

            }
        }
        return sum;
    }

    /**
     * 验证字符的合法性
     * @param chars
     * @return
     */
    public static boolean isValid(char[] chars) {
        if (chars.length == 0) return false;

        for (int i = 0; i < chars.length; i=i+2) {
            if (chars[i] != '0' && chars[i] != '1') {
                return false;
            }
        }
        for (int i = 1; i < chars.length; i=i+2) {
            if (chars[i] != '^' && chars[i] != '&' && chars[i] != '|') {
                return false;
            }
        }

        return true;
    }

    public static boolean logic(boolean o1, boolean o2, char operator) {
        if (operator == '^') {
            return o1 ^ o2;
        } else if (operator == '&') {
            return o1 & o2;
        } else {
            return o1 | o2;
        }
    }

    public static boolean isOperator(char c) {
        if (c == '^' || c == '&' || c == '|') {
            return true;
        }
        return false;
    }


}
